#include "junix.h"

template <
      typename T=int,
      typename Cmp=std::less<T>
>
struct fix_down
{
	void operator()(T vec[], int pos, int size) {
		int lchild=pos*2+1;
		int rchild=lchild+1;
		int min = pos;
		Cmp cmp;

		if (lchild<size && cmp(vec[lchild],vec[min]))
			min=lchild;
		if (rchild<size && cmp(vec[rchild],vec[min]))
			min=rchild;

		if (min != pos) {
			std::swap(vec[pos], vec[min]);
			operator()(vec, min, size);
		}
	}
};

template <
typename T=int,
typename Cmp=std::less<T>
>
struct fix_up
{
	void operator()(T vec[], int pos) {
		int parent = (pos+1)/2 -1;
		Cmp cmp;
		if (parent>=0 && cmp(vec[pos],vec[parent])) {
			std::swap(vec[pos],vec[parent]);
			operator()(vec, parent);
		}
	}
};

template <
typename T=int,
typename Cmp=std::less<T>
>
struct heapsort {
	void operator()(T vec[], int size) {
		fix_down<T,Cmp> dixdown;
		for (int i=size/2; i>=0; i--) {
			fixdown(vec,i,size);
		}

		int sz = size;
		while (sz>0) {
			std::swap(vec[0],vec[--sz]);
			fixdown(vec,0,sz);
		}
	}
};

template <
typename T=int,
typename Cmp=std::less<T>
>
struct makeheap {
	void operator()(T vec[], int size) {
		fix_down<T,Cmp> fixdown;
		for (int i=size/2; i>=0; i--) {
			fixdown(vec,i,size);
		}
	}
};



//================================================
struct Item {
	Item(std::string s, int c)
		:word(s),count(c)
	{ }


	friend std::ostream& operator<<(std::ostream& os, const Item& it) {
		os<<"("<<it.word<<","<<it.count<<")\n";
		return os;
	}

	bool operator<(const Item& it) const {
		return (count<it.count) ||
			    (count==it.count && word<it.word); 
	}

	std::string word;
	int count;
};

int main(int argc, char **argv)
{
	std::ifstream file("BIGTXT");
	if (!file) {
		std::cerr<<"File open error"<<std::endl;
		exit(EXIT_FAILURE);
	}

	typedef std::map<std::string, int> SMAP;
	SMAP words;
	std::string s;
	while (file>>s) {
		++ words[s];
	}

	jtime T;
	T.start();

	SMAP::iterator pos = words.begin();
	SMAP::iterator end = words.end();
	std::vector<Item> M10;
	for (int i=0;i<10 && pos!=end;++i,++pos) {
		M10.push_back(Item(pos->first,pos->second));
	}

	fix_down<Item> fixdown;
	makeheap<Item>()(&M10[0],M10.size());

	for (;pos!=end;++pos) {
		if (pos->second>M10[0].count) {
			M10[0].count=pos->second;
			M10[0].word=pos->first;
			fixdown(&M10[0],0, M10.size());
		}
	}

	T.end();

	sort(M10.begin(),M10.end());
	std::reverse_copy(M10.begin(),M10.end(),
			std::ostream_iterator<Item>(std::cout));
	T.print();
}
